Longest common prefix

Time: O(NK); Space: O(1); easy*

Write a function to find the longest common prefix (LCP) string amongst an array of strings.

Example 1:

Input: L = [“ABCD”, “ABEF”, “ACEF”]

Output: “A”

Example 2:

Input: L = [“ABCDEFG”, “ABCEFG”, “ABCEFA”]

Output: “ABC”

class Solution1(object):
    def longestCommonPrefix(self, L):
        """
        :type L: List[str]
        :rtype: str
        """
        if not L:
            return ""

        for i in range(len(L[0])):
            for str in L[1:]:
                if i >= len(str) or str[i] != L[0][i]:
                    return L[0][:i]
        return L[0]

s = Solution1()
L = ["ABCD", "ABEF", "ACEF"]
assert s.longestCommonPrefix(L) == "A"
L = ["ABCDEFG", "ABCEFG", "ABCEFA"]
assert s.longestCommonPrefix(L) == "ABC"

See also:

https://leetcode.com/problems/longest-common-prefix

https://www.lintcode.com/problem/longest-common-prefix/description